package com.lun.other.sort;

import java.util.Random;

/**
 * 
 * 快速排序
 * 
 * from《剑指Offer-专项突破版》何海涛著
 * 
 * @author Jallen
 *
 */
public class Quick extends SortingAlgorithm{

	private Random rand = new Random(System.nanoTime());
	
	@Override
	public void sort(int[] nums) {
		sort(nums, 0, nums.length - 1);
	}

	private void sort(int[] nums, int start, int end) {
		if(start >= end)
			return;
		
		int pivot = partition(nums, start, end);
		sort(nums, start, pivot - 1);
		sort(nums, pivot + 1, end);
	}

	private int partition(int[] nums, int start, int end) {
		int randNum = rand.nextInt(end - start + 1) ;
		IntArrayTools.swap(nums, start + randNum, end);
		
		int pivot = start, pivotNum = nums[end];
		for(int i = start; i < end; i++) {
			if(nums[i] < pivotNum) {
				IntArrayTools.swap(nums, pivot++, i);
			}
		}
		IntArrayTools.swap(nums, pivot, end);
		
		return pivot;
	}
	
}
